#ifndef BINARY_TREE_H
#define BINARY_TREE_H
#include<iostream>

//模板类BinaryTree作为基类，内部含有Node模板类和一些必需的功能函数与属性。
template<typename DT>
class BinaryTree
{
    private:
        //模板类Node<DT>作为基类，含有element、left、right三个成员属性。
        template<typename DT>
        class Node
        {
            //设为protected类型，防止其他派生类在继承时无法使用这些属性。
            protected:
                DT element;
                Node *left;
                Node *right;
            public:
                //Node类的构造函数，分左值引用和右值引用。
                Node( const DT & element, Node *left, Node *right )
                    : element{ element }, left{ left }, right{ right } { }
        
                Node( DT && element, Node *left, Node *right )
                    : element{ std::move( element ) }, left{ left }, right{ right } { }
        };

    //定义成protected类型，防止root,clone函数等无法被派生类利用。
    protected:
        //二叉树的根节点root
        Node<DT> *root;

    public:
        //构造函数
        BinaryTree( ) : root{ nullptr }
        { }

        //拷贝构造函数，左值引用。
        BinaryTree( const BinaryTree & rhs ) : root{ nullptr }
        {
            root = clone( rhs.root );
        }

        //移动构造函数，右值引用。
        BinaryTree( BinaryTree && rhs ) : root{ rhs.root }
        {
            rhs.root = nullptr;
        }

        //析构函数
        ~BinaryTree( )
        {
            makeEmpty( );
        }

        //拷贝赋值函数
        BinaryTree & operator=( const BinaryTree & rhs )
        {
            BinaryTree copy = rhs;
            std::swap( *this, copy );
            return *this;
        }

        //移动赋值函数
        BinaryTree & operator=( BinaryTree && rhs )
        {
            std::swap( root, rhs.root );   
            return *this;
        }

        //利用virtual关键字声明，以规范派生类的功能函数定义。
        virtual const DT & findMin() const = 0;  //搜索最小值。
        virtual const DT & findMax() const = 0;  //搜索最大值。
        virtual bool contains(const DT & x) const = 0;  //判断二叉树是否包含此元素。
        virtual bool isEmpty() const = 0;  //判断二叉树是否为空。
        virtual void makeEmpty() = 0;  //清空二叉树。
        virtual void printTree(ostream & out = cout) = 0;  //按顺序打印所有数据。
        virtual void insert(const DT & x) = 0;  //插入某个数据，左值引用。
        virtual void insert(DT && x) = 0;  //插入某个数据，右值引用。
        virtual void remove(const DT & x) = 0;  //移出某个数据，左值引用。
        virtual void remove(DT && x) = 0;  //移出某个数据，右值引用。
        virtual void findValues(const DT & min, const DT & max) = 0;  //寻找区间内的所有数据并打印。
};

//模板类BinarySearchTree作为派生类，继承模板类BinaryTree。
template<typename DT>
class BinarySearchTree : public BinaryTree<DT>
{
    private:
        //BSTNode为inarySearchTree的内部类，继承模板类Node。
        class BSTNode : public Node<DT>
        {
            public:
                //BSTNode的构造函数
                BSTNode( const DT & element, BSTNode *left, BSTNode *right )
                    : element{ element }, left{ left }, right{ right } { }
        
                BSTNode( DT && element, BSTNode *left, BSTNode *right )
                    : element{ std::move( element ) }, left{ left }, right{ right } { }
        };

        //克隆函数clone，用于拷贝构造函数和部分public类型的功能函数。
        //定义部分略。
        BSTNode * clone( BSTNode *t ) const
        { }

    public:
        //构造函数
        BinarySearchTree( ) : root{ nullptr }
        { }

        //拷贝构造函数，左值引用。
        BinarySearchTree( const BinarySearchTree & rhs ) : root{ nullptr }
        {
            root = clone( rhs.root );
        }

        //移动构造函数，右值引用。
        BinarySearchTree( BinarySearchTree && rhs ) : root{ rhs.root }
        {
            rhs.root = nullptr;
        }

        //析构函数
        ~BinarySearchTree( )
        {
            makeEmpty( );
        }

        //拷贝赋值函数
        BinarySearchTree & operator=( const BinarySearchTree & rhs )
        {
            BinarySearchTree copy = rhs;
            std::swap( *this, copy );
            return *this;
        }

        //移动赋值函数
        BinarySearchTree & operator=( BinarySearchTree && rhs )
        {
            std::swap( root, rhs.root );   
            return *this;
        }

        //继承到派生类BinarySearchTree的各种功能函数，在派生类中需要进行定义。
        //函数定义部分略。
        virtual const DT & findMin() const 
        { }

        virtual const DT & findMax() const 
        { }

        virtual bool contains(const DT & x) const 
        { }

        virtual bool isEmpty() const 
        { }

        virtual void makeEmpty(ostream & out = cout) const 
        { }

        virtual void insert(const DT & x) 
        { }

        virtual void insert(DT && x)
        { }

        virtual void remove(const DT & x)
        { }

        virtual void remove(DT && x)
        { }

        virtual void findValues(const DT & min, const DT & max) 
        { }

};

//模板类AvlTree作为派生类，继承模板类BinarySearchTree。
template<typename DT>
class AvlTree : public BinarySearchTree<DT>
{
    private:
        //AvlNode作为AvlTree的内部类，继承模板类BSTNode。
        class AvlNode : public BSTNode<DT>
        {
            protected:
                int height;  //节点所在的高度。
            public:
                //AvlNode的构造函数
                AvlNode( const DT & element, AvlNode *left, AvlNode *right, int h = 0 )
                    : element{ element }, left{ left }, right{ right }, height{ h } { }
        
                AvlNode( DT && element, AvlNode *left, AvlNode *right, int h = 0 )
                    : element{ std::move( element ) }, left{ left }, right{ right }, height{ h } { }
        };

        //克隆函数clone，用于复制子树。
        AvlNode * clone( AvlNode *t ) const
        { }

        //用于平衡Avl，使其满足平衡性质。
        //里面分情况调用单旋转和双旋转的函数。
        void balance( AvlNode * & t )
        { }

        //左孩子的单旋转
        void rotateWithLeftChild( AvlNode * & k1 )
        { }

        //右孩子的单旋转
        void rotateWithRightChild( AvlNode * & k2 )
        { }

        //左孩子的双旋转
        void doubleWithLeftChild( AvlNode * & k3 )
        { }

        //右孩子的双旋转
        void doubleWithRightChild( AvlNode * & k4 )
        { }

        //返回节点的对应高度，用内部成员变量height实现。
        int height( AvlNode *t ) const
        { }

    public:
        //构造函数
        AvlTree( ) : root{ nullptr }
        { }
    
        //拷贝构造函数，左值引用。
        AvlTree( const AvlTree & rhs ) : root{ nullptr }
        {
            root = clone( rhs.root );
        }

        //移动构造函数，右值引用。
        AvlTree( AvlTree && rhs ) : root{ rhs.root }
        {
            rhs.root = nullptr;
        }
    
        //析构函数
        ~AvlTree( )
        {
            makeEmpty( );
        }

        //拷贝赋值函数
        AvlTree & operator=( const AvlTree & rhs )
        {
            AvlTree copy = rhs;
            std::swap( *this, copy );
            return *this;
        }
        
        //移动构造函数
        AvlTree & operator=( AvlTree && rhs )
        {
            std::swap( root, rhs.root );        
            return *this;
        }

        //继承到派生类AvlTree的各种功能函数，需要自行定义。
        virtual const DT & findMin() const
        { }

        virtual const DT & findMax() const
        { }

        virtual bool contains(const DT & x) const
        { }

        virtual bool isEmpty() const
        { }

        virtual void makeEmpty()
        { }

        virtual void printTree(ostream & out = cout)
        { }

        virtual void insert(const DT & x) 
        { }

        virtual void insert(DT && x)
        { }

        virtual void remove(const DT & x) 
        { }

        virtual void remove(DT && x)
        { } 

        virtual void findValues(const DT & min, const DT & max) 
        { }

};

//模板类SplayTree作为派生类，继承模板类BinarySearchTree。
template<typename DT>
class SplayTree : public BinarySearchTree<DT>
{
    private:
        //SplayTreeNode作为SplayTree的内部类，继承模板类BSTNode。
        class SplayTreeNode : public BSTNode<DT>
        {
            public:
                //SplayTreeNode类的构造函数
                SplayTreeNode( const DT & element, SplayTreeNode *left, SplayTreeNode *right )
                    : element{ element }, left{ left }, right{ right } { }
        
                SplayTreeNode( DT && element, SplayTreeNode *left, SplayTreeNode *right )
                    : element{ std::move( element ) }, left{ left }, right{ right } { }                
        };

        //空节点nullNode作为private类型。
        SplayTreeNode *nullNode;

        //克隆函数clone，用于复制子树。
        SplayTreeNode * clone( SplayTreeNode * t ) const
        { }

        //“一”字形旋转函数
        void rotateWithLeftChild( SplayTreeNode * & k1 )
        { }

        //“之”字形旋转函数
        void rotateWithRightChild( SplayTreeNode * & k2 )
        { }

        //对于节点x,根节点t进行展开。
        //其中根据情况调用两种旋转函数。
        void splay( const DT & x, SplayTreeNode * & t )
        { }

    public:
        //构造函数
        SplayTree( )
        {
            nullNode = new SplayTreeNode;
            nullNode->left = nullNode->right = nullNode;
            root = nullNode;
        }

        //拷贝构造函数，左值引用。
        SplayTree( const SplayTree & rhs )
        {
            nullNode = new SplayTreeNode;
            nullNode->left = nullNode->right = nullNode;
            root = clone( rhs.root );
        }

        //移动构造函数，右值引用。
        SplayTree( SplayTree && rhs ) : root{ rhs.root }, nullNode{ rhs.nullNode }
        {
            rhs.root = nullptr;
            rhs.nullNode = nullptr;
        }
    
        //析构函数
        ~SplayTree( )
        {
            makeEmpty( );
            delete nullNode;
        }

        //拷贝赋值函数
        SplayTree & operator=( const SplayTree & rhs )
        {
            SplayTree copy = rhs;
            std::swap( *this, copy );
            return *this;
        }
        
        //移动构造函数
        SplayTree & operator=( SplayTree && rhs )
        {
            std::swap( root, rhs.root );
            std::swap( nullNode, rhs.nullNode );
            return *this;
        }

        //继承到派生类SplayTree的各种功能函数，需要自行定义。
        virtual const DT & findMin() const
        { }

        virtual const DT & findMax() const
        { }

        virtual bool contains(const DT & x) const
        { }

        virtual bool isEmpty() const
        { }

        virtual void makeEmpty()
        { }

        virtual void printTree(ostream & out = cout)
        { }

        virtual void insert(const DT & x) 
        { }

        virtual void insert(DT && x)
        { }

        virtual void remove(const DT & x) 
        { }

        virtual void remove(DT && x)
        { } 

        virtual void findValues(const DT & min, const DT & max) 
        { }
        
};

#endif